Search results for "Structural complexity theory"

showing 5 items of 5 documents

On Physical Problems that are Slightly More Difficult than QMA

2013

We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural computational problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian).

Discrete mathematicsFOS: Computer and information sciencesQuantum PhysicsTheoretical computer scienceCompleteNP-easyFOS: Physical sciences0102 computer and information sciencesComputer Science::Computational ComplexityComputational Complexity (cs.CC)01 natural sciencesPHStructural complexity theoryComputer Science - Computational Complexity010201 computation theory & mathematics0103 physical sciencesAsymptotic computational complexityComplexity classF.1.2Low010306 general physicsQuantum Physics (quant-ph)Quantum complexity theoryMathematics2014 IEEE 29th Conference on Computational Complexity (CCC)
researchProduct

Algorithmic Information Theory and Computational Complexity

2013

We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove sever…

Discrete mathematicsAverage-case complexityAlgorithmic information theoryTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESKolmogorov complexityDescriptive complexity theoryComputational physicsStructural complexity theoryTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonAsymptotic computational complexityComputer Science::Formal Languages and Automata TheoryComputational number theoryMathematics
researchProduct

Non-intersecting Complexity

2006

A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.

PHCombinatoricsAverage-case complexityStructural complexity theoryAsymptotic computational complexityWorst-case complexityComplexity classDescriptive complexity theoryQuantum complexity theoryMathematics
researchProduct

Effects of Kolmogorov complexity present in inductive inference as well

1997

For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.

PHAverage-case complexityDiscrete mathematicsStructural complexity theoryKolmogorov complexityKolmogorov structure functionChain rule for Kolmogorov complexityDescriptive complexity theoryMathematicsQuantum complexity theory
researchProduct

Inductive inference of recursive functions: Complexity bounds

2005

This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference ma…

PHAverage-case complexityDiscrete mathematicsStructural complexity theoryTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESRecursively enumerable languageWorst-case complexityInferenceDescriptive complexity theoryNumberingMathematics
researchProduct